/*
	Name: 金明的预算方案
	Author: There,hello
	Date: 28-10-19 21:32
	Description: Luogu P1064
	Algorithm: 背包
*/
#include <bits/stdc++.h>
using namespace std;
int n, m;
int v[99][5], w[99][5], vv[99], ww[99], f[33333];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1, x, y, z; i <= m; ++i)
	{
		scanf("%d%d%d", &x, &y, &z);
		if (z > 0)
		{
			v[z][++v[z][0]] = x;
			w[z][v[z][0]] = y * x;
		}
		else
		{
			vv[i] = x;
			ww[i] = y * x;
		}
	}
	for (int i = 1; i <= m; ++i)
	{
		if (vv[i])
		{
			for (int j = n; j >= vv[i]; --j)
			{
				f[j] = max(f[j], f[j - vv[i]] + ww[i]);
				if (v[i][0] && j - vv[i] - v[i][1] >= 0)
					f[j] = max(f[j], f[j - vv[i] - v[i][1]] + (ww[i]) + (w[i][1]));
				if (v[i][0] == 2 && j - vv[i] - v[i][2] >= 0)
					f[j] = max(f[j], f[j - vv[i] - v[i][2]] + (ww[i]) + (w[i][2]));
				if (v[i][0] == 2 && j - vv[i] - v[i][1] - v[i][2] >= 0)
					f[j] = max(f[j], f[j - vv[i] - v[i][1] - v[i][2]] + (ww[i]) + (w[i][1]) + (w[i][2]));
			}
		}
	}
	printf("%d", f[n]);
	return 0;
}
